#pragma once
#include<vector>

/*
Function takes to vectors and search for max common subsequence.
Operation time: O(n1*n2).
Memory size:    4*n1 bytes
*/

template<class T> 
void findMaxCommonSubsequence(  typename std::vector<T>::iterator it1Begin, typename std::vector<T>::iterator it1End,
                                typename std::vector<T>::iterator it2Begin, typename std::vector<T>::iterator it2End,
                                typename std::vector<T>::iterator &it1Res, typename std::vector<T>::iterator &it2Res, int &len)
{
    typedef std::vector<T>::iterator ItT;
    std::vector<int> m_prev(it1End-it1Begin, 0), m(it1End-it1Begin, 0);

    it1Res = it1End;
    it2Res = it2End;
    len = 0;

    for (ItT it2=it2Begin; it2!=it2End; ++it2)
    {
        int i = 0;
        for (ItT it1=it1Begin; it1!=it1End; ++it1, ++i)
        {
            if (*it1 == *it2)
            {
                int l = (i>0 ? m_prev[i-1] : 0) + 1;
                m[i] = l;
                if (l > len)
                {
                    len = l;
                    it1Res = it1;
                    it2Res = it2;
                }
            }
            else
            {
                m[i] = 0;
            }
        }
        swap(m_prev, m);
    }

    if (len > 0)
    {
        it1Res -= len-1;
        it2Res -= len-1;
    }
}

enum EnumMergeItemStatus
{
    MIS_NO_CHANGES  = 0x00,
    MIS_NEW         = 0x01,
    MIS_DELETED     = 0x02
};

enum EnumMergeResultFlags
{
    MRF_NO_CHANGES = 0x01,
    MRF_DELETED    = 0x02,
    MRF_NEW        = 0x04
};

struct MergerResultItem
{
    int offs, len, src;
    EnumMergeItemStatus status;

    MergerResultItem(int src0, int offs0, int len0, EnumMergeItemStatus status0)
        : src(src0), offs(offs0), len(len0), status(status0)
    {}
};

typedef std::vector<MergerResultItem> MergerResultVector;

template<class T>
void getMergeResult(    std::vector<T> &v1, typename std::vector<T>::iterator it1Begin, typename std::vector<T>::iterator it1End,
                        std::vector<T> &v2, typename std::vector<T>::iterator it2Begin, typename std::vector<T>::iterator it2End,
                        MergerResultVector &mergeResults, int flags = MRF_NO_CHANGES | MRF_DELETED | MRF_NEW)
{
    typedef std::vector<T>::iterator ItT;

    ItT it1Res, it2Res;
    int len;

    findMaxCommonSubsequence<T>(    it1Begin, it1End,
                                    it2Begin, it2End,
                                    it1Res, it2Res, len);

    if (len > 0)
    {
        getMergeResult<T>(  v1, it1Begin, it1Res,
                            v2, it2Begin, it2Res,
                            mergeResults,
                            flags);

        if (flags & MRF_NO_CHANGES)
        {
            mergeResults.push_back(MergerResultItem(1, it2Res-v2.begin(), len, MIS_NO_CHANGES));
        }

        getMergeResult<T>(  v1, it1Res + len, it1End,
                            v2, it2Res + len, it2End,
                            mergeResults,
                            flags);
    }
    else
    {
        if ((it1Begin != it1End) && (flags & MRF_DELETED))
        {
            mergeResults.push_back(MergerResultItem(0, it1Begin - v1.begin(), it1End-it1Begin, MIS_DELETED));
        }
        if ((it2Begin != it2End) && (flags & MRF_NEW))
        {
            mergeResults.push_back(MergerResultItem(1, it2Begin - v2.begin(), it2End-it2Begin, MIS_NEW));
        }
    }
}
